/*
 * Project: Sudoku Explainer
 * Copyright (C) 2006-2007 Nicolas Juillerat
 * 
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.rules;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.IndirectHint;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.util.BitSetFactory;
import com.onegravity.sudoku.solver.util.Permutations;

public class AlignedPairExclusionProducer extends AlignedSubsetExclusionProducer {

	public AlignedPairExclusionProducer() {
        super(2);
    }

    @Override
    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {

        /*
         * Search for "base" cells that can participate to a exclusion set. For each
         * candidate, collect the potentially excluding cells.
         */
        List<Cell> candidateList = new ArrayList<Cell>();
        Map<Cell, Collection<Cell>> cellExcluders = new LinkedHashMap<Cell, Collection<Cell>>();
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                if (Thread.interrupted()) throw new InterruptedException();
                Cell cell = grid.getCell(x, y);
                if (cell.getPotentialValues().cardinality() >= 2) {
                    boolean hasNakedSingle = false;
                    // Look for potentially excluding cells (whose number of candidates <= degree)
                    Collection<Cell> excludingCells = new ArrayList<Cell>();
                    for (Cell excludingCell : cell.getHouseCells()) {
                        int exclCardinality = excludingCell.getPotentialValues().cardinality();
                        if (exclCardinality == 1) hasNakedSingle = true;
                        else if (exclCardinality == 2) excludingCells.add(excludingCell);
                    }
                    // Optimization: Skip this technique if naked singles are remaining
                    if (!hasNakedSingle && !excludingCells.isEmpty()) {
                        candidateList.add(cell);
                        cellExcluders.put(cell, excludingCells);
                    }
                }
            }
        }

        if (cellExcluders.size()<2 || candidateList.size()!=cellExcluders.size()) return;

        /*
         * Iterate on all permutations of 'degree' cells among the possible base cells
         */
        // First iterate on the first two cells
        Permutations cellSetPerm2 = new Permutations(2, cellExcluders.size());
        Set<Cell> commonExcluders = new LinkedHashSet<Cell>();
        while (cellSetPerm2.hasNext()) {
            if (Thread.interrupted()) throw new InterruptedException();
            int[] indexes = cellSetPerm2.nextBitNums();
            // Setup the first two cells
            Cell cell0 = candidateList.get(indexes[0]);
            Cell cell1 = candidateList.get(indexes[1]);

            // Build the list of common excluding cells for the base cells 'cells'
            commonExcluders.clear();
            Collection<Cell> excludingCells = cellExcluders.get(cell0);
            if (excludingCells!=null) {
            	commonExcluders.addAll(excludingCells);
            }
            excludingCells = cellExcluders.get(cell1);
            if (excludingCells!=null) {
                commonExcluders.retainAll(excludingCells);
            }
            if (commonExcluders.size() >= 2) {
                List<int[]> allowedPotentialCombinations = new ArrayList<int[]>();
                Map<int[], Cell> lockedPotentialCombinations = new LinkedHashMap<int[], Cell>();
                BitSet v0 = cell0.getPotentialValues();
                BitSet v1 = cell1.getPotentialValues();

                // Iterate on combinations of potentials accross the base cells
                for (int pt0 = v0.nextSetBit(0); pt0 >= 0; pt0 = v0.nextSetBit(pt0 + 1)) {
                    for (int pt1 = v1.nextSetBit(0); pt1 >= 0; pt1 = v1.nextSetBit(pt1 + 1)) {
                        boolean isAllowed = true;
                        Cell lockingCell = null;

                        // Check if this potential combination is allowed, hidden single rule
                        if (pt0 == pt1 && cell0.getHouseCells().contains(cell1)) {
                        	isAllowed = false;
                        }

                        // Check if this potential combination is allowed, using common excluder cells
                        if (isAllowed) {
                            for (Cell excludingCell : commonExcluders) {
                            	boolean hasMorePotentials = false;
                            	BitSet excludingPotentials = excludingCell.getPotentialValues();
                                for (int n=excludingPotentials.nextSetBit(0); n>=0; n=excludingPotentials.nextSetBit(n+1)) {
                            		if (!(n==pt0 || n==pt1)) {
                            			hasMorePotentials = true;
                            			break;
                            		}
                            	}
                                if (!hasMorePotentials) {
                                    lockingCell = excludingCell;
                                    isAllowed = false;
                                    break;
                                }

                                // old code replaced to save some memory 
                                /*BitSet values = (BitSet)excludingCell.getPotentialValues().clone();
                                values.clear(pt0);
                                values.clear(pt1);
                                if (values.isEmpty()) {
                                    lockingCell = excludingCell;
                                    isAllowed = false;
                                    break;
                                }*/
                            }
                        }

                        // Store the combination in the appropriate structure
                        if (isAllowed) {
                        	allowedPotentialCombinations.add( new int[] {pt0, pt1} );
                        }
                        else {
                        	lockedPotentialCombinations.put(new int[] {pt0, pt1}, lockingCell);
                        }
                    } // for p1
                } // for p0

                /*
                 * For all potentials of all base cells, test if the value is possible
                 * in at least one allowed combination
                 */
                Map<Cell, BitSet> removablePotentials = new HashMap<Cell, BitSet>();
                for (int i = 0; i < 2; i++) {
                    Cell cell = (i==0) ? cell0 : cell1;
                    BitSet values = cell.getPotentialValues();
                    for (int p = values.nextSetBit(0); p >= 0; p = values.nextSetBit(p + 1)) {
                        boolean isValueAllowed = false;
                        for (int[] combinations : allowedPotentialCombinations) {
                            if (combinations[i] == p) {
                                isValueAllowed = true; // At least one allowed combination permits this value
                                break;
                            }
                        }
                        if (!isValueAllowed) {
                            // Yeah, value 'p' can be excluded from cell 'cell'
                            if (removablePotentials.containsKey(cell)) {
                            	removablePotentials.get(cell).set(p);
                            }
                            else {
                            	removablePotentials.put(cell, BitSetFactory.createOneElement(p));
                            }
                        }
                    }
                }

                // Create hint
                IndirectHint hint = new AlignedSubsetExclusionHint(removablePotentials, new Cell[] {cell0, cell1},
                												   lockedPotentialCombinations, grid.hasExtraRegions(), grid.isJigsaw());
                if (hint.isWorth()) accu.add(hint);
            } // if enough common excluders
        } // Iterate on cell permutations

    }

}